104. Maximum Depth of Binary Tree
Easy

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Example 3:

Input: root = []
Output: 0

Example 4:

Input: root = [0]
Output: 1

 

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -100 <= Node.val <= 100
Accepted
1,176,381
Submissions
1,706,235
Seen this question in a real interview before?
Companies

Average Rating: 4.44 (52 votes)

Premium

Solution

Tree definition

First of all, here is the definition of the TreeNode which we would use.




Approach 1: Recursion

Intuition By definition, the maximum depth of a binary tree is the maximum number of steps to reach a leaf node from the root node.

From the definition, an intuitive idea would be to traverse the tree and record the maximum depth during the traversal.

Algorithm

Current
1 / 10

One could traverse the tree either by Depth-First Search (DFS) strategy or Breadth-First Search (BFS) strategy. For this problem, either way would do. Here we demonstrate a solution that is implemented with the DFS strategy and recursion.

Complexity analysis

  • Time complexity : we visit each node exactly once, thus the time complexity is O(N)\mathcal{O}(N), where NN is the number of nodes.

  • Space complexity : in the worst case, the tree is completely unbalanced, e.g. each node has only left child node, the recursion call would occur NN times (the height of the tree), therefore the storage to keep the call stack would be O(N)\mathcal{O}(N). But in the best case (the tree is completely balanced), the height of the tree would be log(N)\log(N). Therefore, the space complexity in this case would be O(log(N))\mathcal{O}(\log(N)).


Approach 2: Tail Recursion + BFS

One might have noticed that the above recursion solution is probably not the most optimal one in terms of the space complexity, and in the extreme case the overhead of call stack might even lead to stack overflow.

To address the issue, one can tweak the solution a bit to make it tail recursion, which is a specific form of recursion where the recursive call is the last action in the function.

The benefit of having tail recursion, is that for certain programming languages (e.g. C++) the compiler could optimize the memory allocation of call stack by reusing the same space for every recursive call, rather than creating the space for each one. As a result, one could obtain the constant space complexity O(1)\mathcal{O}(1) for the overhead of the recursive calls.

Here is a sample solution. Note that the optimization of tail recursion is not supported by Python or Java.

Complexity analysis

  • Time complexity : O(N)\mathcal{O}(N), still we visit each node once and only once.

  • Space complexity : O(2(log2N1))=O(N/2)=O(N)\mathcal{O}(2^{(log_2N-1)})=\mathcal{O}(N/2)=\mathcal{O}(N), i.e. the maximum number of nodes at the same level (the number of leaf nodes in a full binary tree), since we traverse the tree in the BFS manner.

As one can see, this probably is not the best example to apply the tail recursion technique. Because though we did gain the constant space complexity for the recursive calls, we pay the price of O(N)\mathcal{O}(N) complexity to maintain the state information for recursive calls. This defeats the purpose of applying tail recursion.

However, we would like to stress on the point that tail recursion is a useful form of recursion that could eliminate the space overhead incurred by the recursive function calls.

Note: a function cannot be tail recursion if there are multiple occurrences of recursive calls in the function, even if the last action is the recursive call. Because the system has to maintain the function call stack for the sub-function calls that occur within the same function.


Approach 3: Iteration

Intuition

We could also convert the above recursion into iteration, with the help of the stack data structure. Similar with the behaviors of the function call stack, the stack data structure follows the pattern of FILO (First-In-Last-Out), i.e. the last element that is added to a stack would come out first.

With the help of the stack data structure, one could mimic the behaviors of function call stack that is involved in the recursion, to convert a recursive function to a function with iteration.

Algorithm

The idea is to keep the next nodes to visit in a stack. Due to the FILO behavior of stack, one would get the order of visit same as the one in recursion.

We start from a stack which contains the root node and the corresponding depth which is 1. Then we proceed to the iterations: pop the current node out of the stack and push the child nodes. The depth is updated at each step.

Complexity analysis

  • Time complexity : O(N)\mathcal{O}(N).

  • Space complexity : in the worst case, the tree is completely unbalanced, e.g. each node has only left child node, the recursion call would occur NN times (the height of the tree), therefore the storage to keep the call stack would be O(N)\mathcal{O}(N). But in the average case (the tree is balanced), the height of the tree would be log(N)\log(N). Therefore, the space complexity in this case would be O(log(N))\mathcal{O}(\log(N)).

Report Article Issue

Comments: 45
SanD91's avatar
Read More

An easier approach for iterative would be to use BFS instead of any need to store depth in the stack.

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
	Deque<TreeNode> dq = new ArrayDeque<>();
        int depth = 0, next = 0;
        TreeNode cur;
        dq.offer(root);
        
        while (!dq.isEmpty()) {
            depth++;
            next = dq.size();
            for (int i = 0; i < next; ++i) {
                cur = dq.poll();
                if (cur.left != null) dq.offer(cur.left);
                if (cur.right != null) dq.offer(cur.right);
            }
        }
        return depth;
    }
}

112
Show 8 replies
Reply
Share
Report
lenchen1112's avatar
Read More

Python 3 one line

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return max(map(self.maxDepth, [root.left, root.right])) + 1 if root else 0

40
Show 2 replies
Reply
Share
Report
elazar's avatar
Read More

I think the second JAVA solution is BFS and not a DFS, for DFS you need to call to remoeLast

25
Show 6 replies
Reply
Share
Report
vdhyani96's avatar
Read More

Another version of approach 1 easier to understand (Python3):

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        left_height = 1 + self.maxDepth(root.left)
        right_height = 1 + self.maxDepth(root.right)
        return max(left_height , right_height)

13
Show 1 reply
Reply
Share
Report
jehon777's avatar
Read More

Why is approach 3 space complexity O(N) in the worst case? if you have only left child nodes your stack would never be bigger than 1 right? (e.g. add 1, pop 1, for each iteration) please correct me if I am wrong

12
Show 8 replies
Reply
Share
Report
ptn32's avatar
Read More

I thought if there is just the root node the depth would be 0? Why is it 1?

4
Show 3 replies
Reply
Share
Report
Stargarth's avatar
Read More

One line solution in java:

class Solution {
    public int maxDepth(TreeNode root) {
        return root==null ? 0 : Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1);
    }
}

2
Show 2 replies
Reply
Share
Report
aghalarov's avatar
Read More

Hi,
This code is not working in computer.How we can implement this tree which is can debug in computer not leetcode?

1
Show 1 reply
Reply
Share
Report
starlord's avatar
Read More

when the second solution run takes 5 ms and seems very slow?

1
Show 1 reply
Reply
Share
Report
WilmerKrisp's avatar
Read More

Wrong abbreviation in the Approach 3 ! not FILO!
Stack is well known LIFO https://en.wikipedia.org/wiki/LIFO

1
Reply
Share
Report
Success
Details
Runtime: 4 ms, faster than 93.60% of C++ online submissions for Maximum Depth of Binary Tree.
Memory Usage: 18.8 MB, less than 52.36% of C++ online submissions for Maximum Depth of Binary Tree.
Time Submitted
Status
Runtime
Memory
Language
06/19/2021 09:01Accepted4 ms18.8 MBcpp
06/19/2021 09:00Accepted4 ms18.9 MBcpp
06/18/2020 08:50Accepted16 ms19.5 MBcpp
06/06/2020 19:45Accepted12 ms19.3 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.